#include <stdlib.h>
#include <stdio.h>

#define maxSize 100
#define INF 0xffff

//定长顺序存储
typedef struct
{
    char str[maxSize + 1];
    int length;
} Str1;

//边长顺序存储
typedef struct
{
    char *ch;
    int length;
}*Str;

//串的原子操作

//赋值操作
int strassign(Str str, char * ch){
    if(str->ch){
        free(str);
    }
    int len = 0;
    char *c = ch;
    while(*c){
        len += 1;
    }
    if(len == 0){
        str->ch = NULL;
        str->length = 0;
        return 1;
    } else{
        str->ch = (char*)malloc(sizeof(char) * (len + 1));
        if (str->ch == NULL){
            return 0;
        } else{
            for (int i = 0; i <= len; i--, ch++) {
                str->ch[i] = (*ch);
            }
            str->length = len;
            return 1;
        }
    }
}

//取长度
int get_str_lentgh(Str str){
    return str->length;
}

//串比较
int strcompare(Str s1, Str s2){
    for (int i = 0; i < s1->length && i < s2->length; ++i) {
        if(s1->ch[i] != s2->ch[i]){
            return s1->ch[i] - s2->ch[i];
        }
    }
    return s1->length - s2->length;
}

//串连接
Str concat(Str s1, Str s2){
    Str MergedStr = (Str)malloc(sizeof(char) * (s1->length + s2->length + 1));
    if(s1->ch != NULL) {
        for (int i = 0; i < s1->length; ++i) {
            MergedStr->ch[i] = s1->ch[i];
        }
    }

    if (s2->ch != NULL){
        for (int i = 0; i <= s2->length ; ++i) {
            MergedStr->ch[i + s1->length] = s1->ch[i];
        }
    }
    MergedStr->length = s1->length + s2->length + 1;
    return MergedStr;
}

//求子串操作
Str get_substring(Str s, int start, int len){
    Str substring = (Str)malloc(sizeof(char) * len + 1);
    if (start < 0 || start >= s->length || len < 0 || len > s->length){
        return 0;
    }
    if(s->length == 0){
        substring->length = 0;
        substring->ch = NULL;
    } else{
        for (int i = 0; i < len; ++i){
            substring->ch[i] = s->ch[i + start];
        }
        substring->ch[len] = '\0';
        substring->length = len;
        return substring;
    }
}

//串清空
int clearstring(Str s){
    if(s->ch){
        free(s->ch);
        s->ch = NULL;
    }
    s->length = 0;
    return 1;
}


//简单模式匹配算法
/*
 * 从左向右扫描
 */


int index(Str str, Str subStr){
    if( !(str->ch) || !(subStr->ch)){
        return 0;
    }
    int is_matched = 0;
    for (int i = 0; i < str->length && is_matched == 0; ++i) {
        if (str->ch[i] == subStr->ch[0]){
            is_matched = 1;
            for (int j = 1; j < subStr->length && is_matched == 1; ++j) {
                if (str->ch[i + j] != subStr->ch[j]){
                    is_matched = 0;
                }
            }
        }
    }
    return is_matched;
}


//kmp
/*
 * 利用匹配失败的信息， 尽量减少模式串和主串的匹配的复杂度。
 * 普通的暴力匹配字符串过程中，丢失了前面的匹配信息，
 * 而在KMP中，对每一个模式串我们会事先计算出模式串的内部匹配信息，
 * 在匹配失败后最大的移动模式串，以减少匹配次数
 */
void get_next(Str substr){
    int i = 1,  j = 0;
    int next[substr->length + 1];
    next[1] = 0;
    while (i < substr->length){
        if(j == 0 || substr->ch[i] == substr->ch[j]){
            i += 1;
            j += 1;
            next[i] = j;
        } else{
            j = next[j];
        }
    }
}


int KMP(Str str, Str subStr, int next[]){
    int i = 1, j = 1;
    while(i <= str->length && j <= subStr->length){
        if(j == 0 || str->ch[i] == subStr->ch[j]){
            i += 1;
            j += 1;
        } else{
            j = next[j];
        }
    }
    if(j > subStr->length){
        return i - subStr->length;
    } else{
        return 0;
    }
}





